﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Diagnostics.Contracts;
#if !SILVERLIGHT
using System.Runtime.Serialization;
#endif
using System.Security.Permissions;
using System.Text;
using System.Diagnostics.CodeAnalysis;
using System.Security;
using Net.System;
#if SILVERLIGHT
using System.Core; // for System.Core.SR
#endif

namespace Net.System
{
    internal class HashSetExDebugView<T>
    {
        private readonly HashSetEx<T> set;

        public HashSetExDebugView(HashSetEx<T> set)
        {
            this.set = set;
        }

        [DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
        public T[] Items => set.ToArray();
    }

    [DebuggerTypeProxy(typeof(HashSetExDebugView<>))]
    [DebuggerDisplay("Count = {Count}")]
#if !SILVERLIGHT
    [Serializable]
#endif
    public class HashSetEx<T> : ICollection<T>, ISet<T>, IReadOnlyCollection<T>
    {
        // 存储哈希码的低31位
        private const int Lower31BitMask = 0x7FFFFFFF;
        // 切断点，超过此值将不使用栈分配。这对应于100个整数。
        private const int StackAllocThreshold = 100;
        // 从现有集合构造哈希集时，集合可能包含重复项，
        // 因此这用作容量与计数的最大可接受比率。
        // 注意，这仅在构造函数中使用，而不会在哈希集有很多添加后删除操作时自动收缩。
        // 用户必须显式调用TrimExcess来收缩。
        // 设置为3是因为容量可以接受为2倍并向上取整到最近的质数。
        private const int ShrinkThreshold = 3;

#if !SILVERLIGHT
        // constants for serialization
        private const string CapacityName = "Capacity";
        private const string ElementsName = "Elements";
        private const string ComparerName = "Comparer";
        private const string VersionName = "Version";
#endif

        private int[] m_buckets;
        private Slot[] m_slots;
        private int m_count;
        private int m_lastIndex;
        private int m_freeList;
        private readonly IEqualityComparer<T> m_comparer;

        public T this[int index]
        {
            get
            {
                int bucket = m_buckets[index];
                return m_slots[bucket].value;
            }
        }

        #region Constructors

        public HashSetEx() : this(comparer: null) { }

        public HashSetEx(int capacity) : this(capacity, null) { }

        public HashSetEx(IEqualityComparer<T> comparer)
        {
            m_comparer = comparer ?? EqualityComparer2<T>.CreateDefaultEqualityComparer();
            m_lastIndex = 0;
            m_count = 0;
            m_freeList = -1;
        }

        public HashSetEx(IEnumerable<T> collection) : this(collection, null) { }

        /// <summary>
        /// 实现说明:
        /// 由于调整大小相对昂贵（需要重新哈希），此方法尝试通过根据集合大小设置初始容量来最小化调整大小的需求。
        /// </summary>
        /// <param name="collection"></param>
        /// <param name="comparer"></param>
        public HashSetEx(IEnumerable<T> collection, IEqualityComparer<T> comparer) : this(comparer)
        {
            if (collection is HashSetEx<T> otherAsHashSetEx && AreEqualityComparersEqual(this, otherAsHashSetEx))
            {
                CopyFrom(otherAsHashSetEx);
            }
            else
            {
                // to avoid excess resizes, first set size based on collection's count. Collection
                // may contain duplicates, so call TrimExcess if resulting hashset is larger than
                // threshold
                int suggestedCapacity = collection is not ICollection<T> coll ? 0 : coll.Count;
                Initialize(suggestedCapacity);

                UnionWith(collection);

                if (m_count > 0 && m_slots.Length / m_count > ShrinkThreshold)
                {
                    TrimExcess();
                }
            }
        }

        // 从具有相同元素类型和相等比较器的另一个HashSetEx初始化HashSetEx
        private void CopyFrom(HashSetEx<T> source)
        {
            int count = source.m_count;
            if (count == 0)
            {
                // 除了对已完成的工作进行短路处理外，
                // 这还可以避免在otherAsHashSetEx.m_buckets或otherAsHashSetEx.m_slots未初始化时
                // 尝试访问它们时出现的错误。
                return;
            }

            int capacity = source.m_buckets.Length;
            int threshold = HashHelpers.ExpandPrime(count + 1);

            if (threshold >= capacity)
            {
                m_buckets = (int[])source.m_buckets.Clone();
                m_slots = (Slot[])source.m_slots.Clone();

                m_lastIndex = source.m_lastIndex;
                m_freeList = source.m_freeList;
            }
            else
            {
                int lastIndex = source.m_lastIndex;
                Slot[] slots = source.m_slots;
                Initialize(count);
                int index = 0;
                for (int i = 0; i < lastIndex; ++i)
                {
                    int hashCode = slots[i].hashCode;
                    if (hashCode >= 0)
                    {
                        AddValue(index, hashCode, slots[i].value);
                        ++index;
                    }
                }
                Debug.Assert(index == count);
                m_lastIndex = index;
            }
            m_count = count;
        }

        public HashSetEx(int capacity, IEqualityComparer<T> comparer) : this(comparer)
        {
            if (capacity > 0)
            {
                Initialize(capacity);
            }
        }

        #endregion

        #region ICollection<T> methods

        /// <summary>
        /// 向此哈希集中添加项目。这是ICollection-T接口的显式实现。
        /// 另一个Add方法返回bool值，指示项目是否已添加。
        /// </summary>
        /// <param name="item">要添加的项目</param>
        void ICollection<T>.Add(T item)
        {
            AddIfNotPresent(item);
        }

        /// <summary>
        /// 从此集合中移除所有项目。这将清除元素但不清除底层的buckets和slots数组。
        /// 调用此方法后应调用TrimExcess来释放这些资源。
        /// </summary>
        public virtual void Clear()
        {
            if (m_lastIndex > 0)
            {
                Debug.Assert(m_buckets != null, "m_buckets was null but m_lastIndex > 0");

                // 清除元素以便垃圾回收器可以回收引用。
                // 只清除m_slots中直到m_lastIndex的部分
                Array.Clear(m_slots, 0, m_lastIndex);
                Array.Clear(m_buckets, 0, m_buckets.Length);
                m_lastIndex = 0;
                m_count = 0;
                m_freeList = -1;
            }
        }

        /// <summary>
        /// 检查此哈希集中是否包含该项目
        /// </summary>
        /// <param name="item">要检查是否包含的项目</param>
        /// <returns>如果包含该项目则返回true；否则返回false</returns>
        public bool Contains(T item)
        {
            int hashCode = InternalGetHashCode(item);
            // 请参见"HashSetEx"级别的注释，了解为什么在for循环中出现"- 1"
            for (int i = m_buckets[hashCode % m_buckets.Length] - 1; i >= 0; i = m_slots[i].next)
            {
                if (m_slots[i].hashCode == hashCode && m_comparer.Equals(m_slots[i].value, item))
                {
                    return true;
                }
            }
            // m_buckets为null或未找到
            return false;
        }

        /// <summary>
        /// 将此哈希集中的项目复制到数组中，从arrayIndex开始
        /// </summary>
        /// <param name="array">要添加项目的数组</param>
        /// <param name="arrayIndex">开始的索引</param>
        public void CopyTo(T[] array, int arrayIndex)
        {
            CopyTo(array, arrayIndex, m_count);
        }

        /// <summary>
        /// 从此哈希集中移除项目
        /// </summary>
        /// <param name="item">要移除的项目</param>
        /// <returns>如果移除成功则返回true；否则返回false（即项目不在HashSetEx中）</returns>
        public virtual bool Remove(T item)
        {
            int hashCode = InternalGetHashCode(item);
            int bucket = hashCode % m_buckets.Length;
            int last = -1;
            for (int i = m_buckets[bucket] - 1; i >= 0; last = i, i = m_slots[i].next)
            {
                if (m_slots[i].hashCode == hashCode && m_comparer.Equals(m_slots[i].value, item))
                {
                    if (last < 0)
                    {
                        // first iteration; update buckets
                        m_buckets[bucket] = m_slots[i].next + 1;
                    }
                    else
                    {
                        // subsequent iterations; update 'next' pointers
                        m_slots[last].next = m_slots[i].next;
                    }
                    m_slots[i].hashCode = -1;
                    m_slots[i].value = default;
                    m_slots[i].next = m_freeList;

                    m_count--;
                    if (m_count == 0)
                    {
                        m_lastIndex = 0;
                        m_freeList = -1;
                    }
                    else
                    {
                        m_freeList = i;
                    }
                    return true;
                }
            }
            // either m_buckets is null or wasn't found
            return false;
        }

        /// <summary>
        /// 获取集合中元素的数量
        /// </summary>
        public int Count => m_count;

        /// <summary>
        /// 是否为只读
        /// </summary>
        bool ICollection<T>.IsReadOnly
        {
            get { return false; }
        }

        #endregion

        #region IEnumerable methods

        public Enumerator GetEnumerator()
        {
            return new Enumerator(this);
        }

        IEnumerator<T> IEnumerable<T>.GetEnumerator()
        {
            return new Enumerator(this);
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return new Enumerator(this);
        }

        #endregion

        #region HashSetEx methods

        /// <summary>
        /// 向此HashSetEx添加项目。返回bool值指示项目是否已添加（如果已存在则不会添加）
        /// </summary>
        /// <param name="item"></param>
        /// <returns>如果添加成功则返回true，如果已存在则返回false</returns>
        public virtual bool Add(T item)
        {
            return AddIfNotPresent(item);
        }

        /// <summary>
        /// 在集合中搜索给定值并返回找到的相等值（如果有的话）。
        /// </summary>
        /// <param name="equalValue">要搜索的值。</param>
        /// <param name="actualValue">从集合中找到的值，如果搜索未匹配则为<typeparamref name="T"/>的默认值。</param>
        /// <returns>指示搜索是否成功的值。</returns>
        /// <remarks>
        /// 当您想重用先前存储的引用而不是新构造的引用时（以便更多地共享引用），
        /// 或者查找具有比您当前拥有的值更完整数据的值时，这可能很有用，
        /// 尽管它们的比较器函数表明它们是相等的。
        /// </remarks>
        public bool TryGetValue(T equalValue, out T actualValue)
        {
            int i = InternalIndexOf(equalValue);
            if (i >= 0)
            {
                actualValue = m_slots[i].value;
                return true;
            }
            actualValue = default;
            return false;
        }

        /// <summary>
        /// 将此HashSetEx与其他集合取并集。修改此集合。
        /// 
        /// 实现说明：GetSuggestedCapacity（提前增加容量以避免多次调整大小）
        /// 在实践中最终并不有用；很快就会达到浪费检查的程度。
        /// </summary>
        /// <param name="other">要添加元素的可枚举集合</param>
        public void UnionWith(IEnumerable<T> other)
        {
            if (other == null)
            {
                throw new ArgumentNullException("other");
            }
            Contract.EndContractBlock();

            foreach (T item in other)
            {
                AddIfNotPresent(item);
            }
        }

        /// <summary>
        /// 将此集合与其他集合取交集。修改此集合。
        /// 
        /// 实现说明：
        /// 如果other是使用相同相等比较器的哈希集，我们会获得更好的性能，
        /// 因为在other中获得常量包含检查。结果成本是O(n1)来遍历此集合。
        /// 
        /// 如果我们不能采用上述路线，则遍历other并通过检查此集合中的包含来标记交集。
        /// 然后循环并删除任何未标记的元素。总成本是n2+n1。
        /// 
        /// 尝试仅基于计数提前返回，利用任何集合与空集的交集都是空集的属性。
        /// </summary>
        /// <param name="other">要进行交集运算的可枚举集合</param>
        public void IntersectWith(IEnumerable<T> other)
        {
            if (other == null)
            {
                throw new ArgumentNullException("other");
            }
            Contract.EndContractBlock();

            // intersection of anything with empty set is empty set, so return if count is 0
            if (m_count == 0)
            {
                return;
            }

            // if other is empty, intersection is empty set; remove all elements and we're done
            // can only figure this out if implements ICollection<T>. (IEnumerable<T> has no count)
            ICollection<T> otherAsCollection = other as ICollection<T>;
            if (otherAsCollection != null)
            {
                if (otherAsCollection.Count == 0)
                {
                    Clear();
                    return;
                }

                HashSetEx<T> otherAsSet = other as HashSetEx<T>;
                // faster if other is a hashset using same equality comparer; so check 
                // that other is a hashset using the same equality comparer.
                if (otherAsSet != null && AreEqualityComparersEqual(this, otherAsSet))
                {
                    IntersectWithHashSetExWithSameEC(otherAsSet);
                    return;
                }
            }

            IntersectWithEnumerable(other);
        }

        /// <summary>
        /// 从此集合中移除other中的项目。修改此集合。
        /// </summary>
        /// <param name="other">要进行差集运算的可枚举集合</param>
        public void ExceptWith(IEnumerable<T> other)
        {
            if (other == null)
            {
                throw new ArgumentNullException("other");
            }
            Contract.EndContractBlock();

            // 这已经是空集；返回
            if (m_count == 0)
            {
                return;
            }

            // 特殊情况：如果other是this；集合减去自身是空集
            if (other == this)
            {
                Clear();
                return;
            }

            // 从this中移除other中的每个元素
            foreach (T element in other)
            {
                Remove(element);
            }
        }

        /// <summary>
        /// 与other和此集合取对称差集（XOR）。修改此集合。
        /// </summary>
        /// <param name="other">要进行对称差集运算的可枚举集合</param>
        public void SymmetricExceptWith(IEnumerable<T> other)
        {
            if (other == null)
            {
                throw new ArgumentNullException("other");
            }
            Contract.EndContractBlock();

            // if set is empty, then symmetric difference is other
            if (m_count == 0)
            {
                UnionWith(other);
                return;
            }

            // special case this; the symmetric difference of a set with itself is the empty set
            if (other == this)
            {
                Clear();
                return;
            }

            HashSetEx<T> otherAsSet = other as HashSetEx<T>;
            // If other is a HashSetEx, it has unique elements according to its equality comparer,
            // but if they're using different equality comparers, then assumption of uniqueness
            // will fail. So first check if other is a hashset using the same equality comparer;
            // symmetric except is a lot faster and avoids bit array allocations if we can assume
            // uniqueness
            if (otherAsSet != null && AreEqualityComparersEqual(this, otherAsSet))
            {
                SymmetricExceptWithUniqueHashSetEx(otherAsSet);
            }
            else
            {
                SymmetricExceptWithEnumerable(other);
            }
        }

        /// <summary>
        /// 检查此集合是否为other的子集。
        /// 
        /// 实现说明：
        /// 以下属性用于预先避免元素级检查：
        /// 1. 如果这是空集，则它是任何集合的子集，包括空集
        /// 2. 如果other根据此相等比较器具有唯一元素，且this的元素多于other，
        /// 则它不能是子集。
        /// 
        /// 此外，如果other是使用相同相等比较器的哈希集，
        /// 我们可以使用更快的元素级检查。
        /// </summary>
        /// <param name="other">要进行子集检查的可枚举集合</param>
        /// <returns>如果此集合是other的子集则返回true；否则返回false</returns>
        public bool IsSubsetOf(IEnumerable<T> other)
        {
            if (other == null)
            {
                throw new ArgumentNullException("other");
            }
            Contract.EndContractBlock();

            // 空集是任何集合的子集
            if (m_count == 0)
            {
                return true;
            }

            HashSetEx<T> otherAsSet = other as HashSetEx<T>;
            // 如果other根据此相等比较器具有唯一元素则更快；所以检查
            // other是否是使用相同相等比较器的哈希集。
            if (otherAsSet != null && AreEqualityComparersEqual(this, otherAsSet))
            {
                // 如果this有更多元素则不能是子集
                if (m_count > otherAsSet.Count)
                {
                    return false;
                }

                // 已经检查过我们使用相同的相等比较器。只需检查
                // this中的每个元素是否包含在other中。
                return IsSubsetOfHashSetExWithSameEC(otherAsSet);
            }
            else
            {
                ElementCount result = CheckUniqueAndUnfoundElements(other, false);
                return result.uniqueCount == m_count && result.unfoundCount >= 0;
            }
        }

        /// <summary>
        /// 检查此集合是否为other的真子集（即严格包含在其中）
        /// 
        /// 实现说明：
        /// 以下属性用于预先避免元素级检查：
        /// 1. 如果这是空集，则它是至少包含一个元素的集合的真子集，
        /// 但它不是空集的真子集。
        /// 2. 如果other根据此相等比较器具有唯一元素，且this的元素数量>=
        /// other中的元素数量，则this不能是真子集。
        /// 
        /// 此外，如果other是使用相同相等比较器的哈希集，
        /// 我们可以使用更快的元素级检查。
        /// </summary>
        /// <param name="other">要进行真子集检查的可枚举集合</param>
        /// <returns>如果此集合是other的真子集则返回true；否则返回false</returns>
        public bool IsProperSubsetOf(IEnumerable<T> other)
        {
            if (other == null)
            {
                throw new ArgumentNullException("other");
            }
            Contract.EndContractBlock();

            ICollection<T> otherAsCollection = other as ICollection<T>;
            if (otherAsCollection != null)
            {
                // the empty set is a proper subset of anything but the empty set
                if (m_count == 0)
                {
                    return otherAsCollection.Count > 0;
                }
                HashSetEx<T> otherAsSet = other as HashSetEx<T>;
                // faster if other is a hashset (and we're using same equality comparer)
                if (otherAsSet != null && AreEqualityComparersEqual(this, otherAsSet))
                {
                    if (m_count >= otherAsSet.Count)
                    {
                        return false;
                    }
                    // this has strictly less than number of items in other, so the following
                    // check suffices for proper subset.
                    return IsSubsetOfHashSetExWithSameEC(otherAsSet);
                }
            }

            ElementCount result = CheckUniqueAndUnfoundElements(other, false);
            return result.uniqueCount == m_count && result.unfoundCount > 0;

        }

        /// <summary>
        /// 检查此集合是否为other的超集
        /// 
        /// 实现说明：
        /// 以下属性用于预先避免元素级检查：
        /// 1. 如果other没有元素（它是空集），则这是超集，即使this也是空集。
        /// 2. 如果other根据此相等比较器具有唯一元素，且this的元素少于other中的元素数量，
        /// 则this不能是超集
        /// 
        /// </summary>
        /// <param name="other">要进行超集检查的可枚举集合</param>
        /// <returns>如果此集合是other的超集则返回true；否则返回false</returns>
        public bool IsSupersetOf(IEnumerable<T> other)
        {
            if (other == null)
            {
                throw new ArgumentNullException("other");
            }
            Contract.EndContractBlock();

            // 尝试基于计数提前返回
            ICollection<T> otherAsCollection = other as ICollection<T>;
            if (otherAsCollection != null)
            {
                // 如果other是空集则这是超集
                if (otherAsCollection.Count == 0)
                {
                    return true;
                }
                HashSetEx<T> otherAsSet = other as HashSetEx<T>;
                // 如果other是具有相同相等比较器的哈希集，则尝试仅基于计数进行比较
                if (otherAsSet != null && AreEqualityComparersEqual(this, otherAsSet))
                {
                    if (otherAsSet.Count > m_count)
                    {
                        return false;
                    }
                }
            }

            return ContainsAllElements(other);
        }

        /// <summary>
        /// 检查此集合是否为other的真超集（即other严格包含在此集合中）
        /// 
        /// 实现说明：
        /// 这比上面稍微复杂一些，因为我们必须跟踪是否至少有一个元素不包含在other中。
        /// 
        /// 以下属性用于预先避免元素级检查：
        /// 1. 如果这是空集，则它不能是任何集合的真超集，即使other是空集。
        /// 2. 如果other是空集且this至少包含1个元素，则这是真超集。
        /// 3. 如果other根据此相等比较器具有唯一元素，且other的计数大于或等于此计数，
        /// 则this不能是真超集
        /// 
        /// 此外，如果other根据此相等比较器具有唯一元素，
        /// 我们可以使用更快的元素级检查。
        /// </summary>
        /// <param name="other">要进行真超集检查的可枚举集合</param>
        /// <returns>如果此集合是other的真超集则返回true；否则返回false</returns>
        public bool IsProperSupersetOf(IEnumerable<T> other)
        {
            if (other == null)
            {
                throw new ArgumentNullException("other");
            }
            Contract.EndContractBlock();

            // the empty set isn't a proper superset of any set.
            if (m_count == 0)
            {
                return false;
            }

            ICollection<T> otherAsCollection = other as ICollection<T>;
            if (otherAsCollection != null)
            {
                // if other is the empty set then this is a superset
                if (otherAsCollection.Count == 0)
                {
                    // note that this has at least one element, based on above check
                    return true;
                }
                HashSetEx<T> otherAsSet = other as HashSetEx<T>;
                // faster if other is a hashset with the same equality comparer
                if (otherAsSet != null && AreEqualityComparersEqual(this, otherAsSet))
                {
                    if (otherAsSet.Count >= m_count)
                    {
                        return false;
                    }
                    // now perform element check
                    return ContainsAllElements(otherAsSet);
                }
            }
            // couldn't fall out in the above cases; do it the long way
            ElementCount result = CheckUniqueAndUnfoundElements(other, true);
            return result.uniqueCount < m_count && result.unfoundCount == 0;

        }

        /// <summary>
        /// 检查此集合是否与other重叠（即它们至少共享一个项目）
        /// </summary>
        /// <param name="other">要进行重叠检查的可枚举集合</param>
        /// <returns>如果这些集合至少有一个共同元素则返回true；如果不相交则返回false</returns>
        public bool Overlaps(IEnumerable<T> other)
        {
            if (other == null)
            {
                throw new ArgumentNullException("other");
            }
            Contract.EndContractBlock();

            if (m_count == 0)
            {
                return false;
            }

            foreach (T element in other)
            {
                if (Contains(element))
                {
                    return true;
                }
            }
            return false;
        }

        /// <summary>
        /// 检查此集合和other是否包含相同的元素。这是集合相等性：
        /// 重复项和顺序被忽略
        /// </summary>
        /// <param name="other">要进行相等性比较的可枚举集合</param>
        /// <returns>如果集合包含相同的元素则返回true；否则返回false</returns>
        public bool SetEquals(IEnumerable<T> other)
        {
            if (other == null)
            {
                throw new ArgumentNullException("other");
            }
            Contract.EndContractBlock();

            HashSetEx<T> otherAsSet = other as HashSetEx<T>;
            // faster if other is a hashset and we're using same equality comparer
            if (otherAsSet != null && AreEqualityComparersEqual(this, otherAsSet))
            {
                // attempt to return early: since both contain unique elements, if they have 
                // different counts, then they can't be equal
                if (m_count != otherAsSet.Count)
                {
                    return false;
                }

                // already confirmed that the sets have the same number of distinct elements, so if
                // one is a superset of the other then they must be equal
                return ContainsAllElements(otherAsSet);
            }
            else
            {
                ICollection<T> otherAsCollection = other as ICollection<T>;
                if (otherAsCollection != null)
                {
                    // if this count is 0 but other contains at least one element, they can't be equal
                    if (m_count == 0 && otherAsCollection.Count > 0)
                    {
                        return false;
                    }
                }
                ElementCount result = CheckUniqueAndUnfoundElements(other, true);
                return result.uniqueCount == m_count && result.unfoundCount == 0;
            }
        }

        public void CopyTo(T[] array) => CopyTo(array, 0, m_count);

        public void CopyTo(T[] array, int arrayIndex, int count)
        {
            if (array == null)
            {
                throw new ArgumentNullException("array");
            }
            Contract.EndContractBlock();

            // check array index valid index into array
            if (arrayIndex < 0)
            {
                throw new ArgumentOutOfRangeException("arrayIndex");
            }

            // also throw if count less than 0
            if (count < 0)
            {
                throw new ArgumentOutOfRangeException("count");
            }

            // will array, starting at arrayIndex, be able to hold elements? Note: not
            // checking arrayIndex >= array.Length (consistency with list of allowing
            // count of 0; subsequent check takes care of the rest)
            if (arrayIndex > array.Length || count > array.Length - arrayIndex)
            {
                throw new ArgumentException();
            }

            int numCopied = 0;
            for (int i = 0; i < m_lastIndex && numCopied < count; i++)
            {
                if (m_slots[i].hashCode >= 0)
                {
                    array[arrayIndex + numCopied] = m_slots[i].value;
                    numCopied++;
                }
            }
        }

        /// <summary>
        /// 移除与指定谓词匹配的元素。返回移除的元素数量
        /// </summary>
        /// <param name="match">用于定义要移除的元素的谓词</param>
        /// <returns>移除的元素数量</returns>
        public virtual int RemoveWhere(Predicate<T> match)
        {
            if (match == null)
            {
                throw new ArgumentNullException("match");
            }
            Contract.EndContractBlock();

            int numRemoved = 0;
            for (int i = 0; i < m_lastIndex; i++)
            {
                if (m_slots[i].hashCode >= 0)
                {
                    // cache value in case delegate removes it
                    T value = m_slots[i].value;
                    if (match(value))
                    {
                        // check again that remove actually removed it
                        if (Remove(value))
                        {
                            numRemoved++;
                        }
                    }
                }
            }
            return numRemoved;
        }

        /// <summary>
        /// 获取用于确定 HashSetEx 中键相等性的 IEqualityComparer
        /// </summary>
        public IEqualityComparer<T> Comparer => m_comparer;

        /// <summary>
        /// 将此列表的容量设置为列表的大小（向上舍入到最近的质数），
        /// 除非计数为0，在这种情况下我们释放引用。
        /// 
        /// 一旦知道不会向列表添加新元素，此方法可用于最小化列表的内存开销。
        /// 要完全清除列表并释放列表引用的所有内存，请执行以下语句：
        /// 
        /// list.Clear();
        /// list.TrimExcess(); 
        /// </summary>
        public void TrimExcess()
        {
            Debug.Assert(m_count >= 0, "m_count is negative");

            if (m_count == 0)
            {
                // if count is zero, clear references
                m_buckets = null;
                m_slots = null;
            }
            else
            {
                Debug.Assert(m_buckets != null, "m_buckets was null but m_count > 0");

                // similar to IncreaseCapacity but moves down elements in case add/remove/etc
                // caused fragmentation
                int newSize = HashHelpers.GetPrime(m_count);
                Slot[] newSlots = new Slot[newSize];
                int[] newBuckets = new int[newSize];

                // move down slots and rehash at the same time. newIndex keeps track of current 
                // position in newSlots array
                int newIndex = 0;
                for (int i = 0; i < m_lastIndex; i++)
                {
                    if (m_slots[i].hashCode >= 0)
                    {
                        newSlots[newIndex] = m_slots[i];

                        // rehash
                        int bucket = newSlots[newIndex].hashCode % newSize;
                        newSlots[newIndex].next = newBuckets[bucket] - 1;
                        newBuckets[bucket] = newIndex + 1;

                        newIndex++;
                    }
                }

                Debug.Assert(newSlots.Length <= m_slots.Length, "capacity increased after TrimExcess");

                m_lastIndex = newIndex;
                m_slots = newSlots;
                m_buckets = newBuckets;
                m_freeList = -1;
            }
        }

#if !SILVERLIGHT || FEATURE_NETCORE
        /// <summary>
        /// 用于HashSetEx测试的深度相等性比较
        /// </summary>
        /// <returns>HashSetEx的相等性比较器</returns>
        public static IEqualityComparer<HashSetEx<T>> CreateSetComparer()
        {
            return new HashSetExEqualityComparer<T>();
        }
#endif

        #endregion

        #region Helper methods

        /// <summary>
        /// 初始化buckets和slots数组。通过找到大于或等于容量的下一个质数来使用建议的容量。
        /// </summary>
        /// <param name="capacity">初始容量</param>
        private void Initialize(int capacity)
        {
            Debug.Assert(m_buckets == null, "Initialize was called but m_buckets was non-null");

            int size = HashHelpers.GetPrime(capacity);

            m_buckets = new int[size];
            m_slots = new Slot[size];
        }

        /// <summary>
        /// 扩展到新容量。新容量是大于或等于建议大小的下一个质数。
        /// 当底层数组被填满时调用此方法。这不执行碎片整理，允许更快的执行；
        /// 注意这是合理的，因为AddIfNotPresent试图在重新打开的位置插入新元素。
        /// </summary>
        /// <param name="sizeSuggestion">建议的大小</param>
        private void IncreaseCapacity()
        {
            Debug.Assert(m_buckets != null, "IncreaseCapacity called on a set with no elements");

            int newSize = HashHelpers.ExpandPrime(m_count);
            if (newSize <= m_count)
            {
                throw new ArgumentException();
            }

            // Able to increase capacity; copy elements to larger array and rehash
            SetCapacity(newSize, false);
        }

        /// <summary>
        /// 将底层数组buckets设置为新大小newSize并重新哈希。
        /// 注意newSize*必须*是质数。
        /// 很可能您想调用IncreaseCapacity()而不是此方法。
        /// </summary>
        private void SetCapacity(int newSize, bool forceNewHashCodes)
        {
            Contract.Assert(HashHelpers.IsPrime(newSize), "New size is not prime!");

            Contract.Assert(m_buckets != null, "SetCapacity called on a set with no elements");

            Slot[] newSlots = new Slot[newSize];
            if (m_slots != null)
            {
                Array.Copy(m_slots, 0, newSlots, 0, m_lastIndex);
            }

            if (forceNewHashCodes)
            {
                for (int i = 0; i < m_lastIndex; i++)
                {
                    if (newSlots[i].hashCode != -1)
                    {
                        newSlots[i].hashCode = InternalGetHashCode(newSlots[i].value);
                    }
                }
            }

            int[] newBuckets = new int[newSize];
            for (int i = 0; i < m_lastIndex; i++)
            {
                int bucket = newSlots[i].hashCode % newSize;
                newSlots[i].next = newBuckets[bucket] - 1;
                newBuckets[bucket] = i + 1;
            }
            m_slots = newSlots;
            m_buckets = newBuckets;
        }

        /// <summary>
        /// 如果尚未包含该值，则将其添加到HashSetEx中
        /// 如果添加成功则返回true，如果已存在则返回false
        /// </summary>
        /// <param name="value">要查找的值</param>
        /// <returns>如果添加成功则返回true，如果已存在则返回false</returns>
        private bool AddIfNotPresent(T value)
        {
            int hashCode = InternalGetHashCode(value);
            int bucket = hashCode % m_buckets.Length;
#if FEATURE_RANDOMIZED_string_HASHING && !FEATURE_NETCORE
            int collisionCount = 0;
#endif
            for (int i = m_buckets[hashCode % m_buckets.Length] - 1; i >= 0; i = m_slots[i].next)
            {
                if (m_slots[i].hashCode == hashCode && m_comparer.Equals(m_slots[i].value, value))
                {
                    return false;
                }
#if FEATURE_RANDOMIZED_string_HASHING && !FEATURE_NETCORE
                collisionCount++;
#endif
            }

            int index;
            if (m_freeList >= 0)
            {
                index = m_freeList;
                m_freeList = m_slots[index].next;
            }
            else
            {
                if (m_lastIndex == m_slots.Length)
                {
                    IncreaseCapacity();
                    // this will change during resize
                    bucket = hashCode % m_buckets.Length;
                }
                index = m_lastIndex;
                m_lastIndex++;
            }
            m_slots[index].hashCode = hashCode;
            m_slots[index].value = value;
            m_slots[index].next = m_buckets[bucket] - 1;
            m_buckets[bucket] = index + 1;
            m_count++;

#if FEATURE_RANDOMIZED_string_HASHING && !FEATURE_NETCORE
            if(collisionCount > HashHelpers.HashCollisionThreshold && HashHelpers.IsWellKnownEqualityComparer(m_comparer)) {
                m_comparer = (IEqualityComparer<T>) HashHelpers.GetRandomizedEqualityComparer(m_comparer);
                SetCapacity(m_buckets.Length, true);
            }
#endif // FEATURE_RANDOMIZED_string_HASHING

            return true;
        }

        // 在已知索引处添加具有已知哈希码的值。仅在从另一个HashSetEx构造时使用。
        private void AddValue(int index, int hashCode, T value)
        {
            int bucket = hashCode % m_buckets.Length;

#if DEBUG
            Debug.Assert(InternalGetHashCode(value) == hashCode);
            for (int i = m_buckets[bucket] - 1; i >= 0; i = m_slots[i].next)
            {
                Debug.Assert(!m_comparer.Equals(m_slots[i].value, value));
            }
#endif

            Debug.Assert(m_freeList == -1);
            m_slots[index].hashCode = hashCode;
            m_slots[index].value = value;
            m_slots[index].next = m_buckets[bucket] - 1;
            m_buckets[bucket] = index + 1;
        }

        /// <summary>
        /// 检查此集合是否包含other的所有元素。遍历other的元素，
        /// 一旦发现other中有不在this中的元素就返回false。
        /// 由SupersetOf、ProperSupersetOf和SetEquals使用。
        /// </summary>
        /// <param name="other">要检查的集合</param>
        /// <returns>如果包含所有元素则返回true，否则返回false</returns>
        private bool ContainsAllElements(IEnumerable<T> other)
        {
            foreach (T element in other)
            {
                if (!Contains(element))
                {
                    return false;
                }
            }
            return true;
        }

        /// <summary>
        /// 实现说明：
        /// 如果other是哈希集并且使用相同的相等比较器，则检查子集会更快。
        /// 只需检查this中的每个元素是否都在other中。
        /// 
        /// 注意：如果other不使用相同的相等比较器，则Contains检查无效，
        /// 这就是为什么调用者必须注意这一点。
        /// 
        /// 如果调用者关心这是否是真子集，他会处理这个问题。
        ///
        /// </summary>
        /// <param name="other">要比较的哈希集</param>
        /// <returns>如果是子集则返回true，否则返回false</returns>
        private bool IsSubsetOfHashSetExWithSameEC(HashSetEx<T> other)
        {

            foreach (T item in this)
            {
                if (!other.Contains(item))
                {
                    return false;
                }
            }
            return true;
        }

        /// <summary>
        /// 如果other是使用相同相等比较器的哈希集，则交集运算会快得多，
        /// 因为我们可以使用other的Contains方法
        /// </summary>
        /// <param name="other">要进行交集运算的哈希集</param>
        private void IntersectWithHashSetExWithSameEC(HashSetEx<T> other)
        {
            for (int i = 0; i < m_lastIndex; i++)
            {
                if (m_slots[i].hashCode >= 0)
                {
                    T item = m_slots[i].value;
                    if (!other.Contains(item))
                    {
                        Remove(item);
                    }
                }
            }
        }

        /// <summary>
        /// 遍历other。如果在this中包含，则在位数组中标记对应于其在m_slots中位置的元素。
        /// 如果有任何未标记的元素（在位数组中），则将其移除。
        /// 
        /// 如果低于StackAllocThreshold，这将尝试在栈上分配。
        /// </summary>
        /// <param name="other">要进行交集运算的可枚举集合</param>
        [SecuritySafeCritical]
        private unsafe void IntersectWithEnumerable(IEnumerable<T> other)
        {
            Debug.Assert(m_buckets != null, "m_buckets shouldn't be null; callers should check first");

            // keep track of current last index; don't want to move past the end of our bit array
            // (could happen if another thread is modifying the collection)
            int originalLastIndex = m_lastIndex;
            int intArrayLength = BitHelper.ToIntArrayLength(originalLastIndex);

            BitHelper bitHelper;
            if (intArrayLength <= StackAllocThreshold)
            {
                int* bitArrayPtr = stackalloc int[intArrayLength];
                bitHelper = new BitHelper(bitArrayPtr, intArrayLength);
            }
            else
            {
                int[] bitArray = new int[intArrayLength];
                bitHelper = new BitHelper(bitArray, intArrayLength);
            }

            // mark if contains: find index of in slots array and mark corresponding element in bit array
            foreach (T item in other)
            {
                int index = InternalIndexOf(item);
                if (index >= 0)
                {
                    bitHelper.MarkBit(index);
                }
            }

            // if anything unmarked, remove it. Perf can be optimized here if BitHelper had a 
            // FindFirstUnmarked method.
            for (int i = 0; i < originalLastIndex; i++)
            {
                if (m_slots[i].hashCode >= 0 && !bitHelper.IsMarked(i))
                {
                    Remove(m_slots[i].value);
                }
            }
        }

        /// <summary>
        /// 由必须依赖位数组标记的集合操作内部使用。这类似于Contains方法，
        /// 但返回的是slots数组中的索引。
        /// </summary>
        /// <param name="item">要查找的项</param>
        /// <returns>项在slots数组中的索引，如果未找到则返回-1</returns>
        private int InternalIndexOf(T item)
        {
            Debug.Assert(m_buckets != null, "m_buckets was null; callers should check first");

            int hashCode = InternalGetHashCode(item);
            for (int i = m_buckets[hashCode % m_buckets.Length] - 1; i >= 0; i = m_slots[i].next)
            {
                if (m_slots[i].hashCode == hashCode && m_comparer.Equals(m_slots[i].value, item))
                {
                    return i;
                }
            }
            // wasn't found
            return -1;
        }

        /// <summary>
        /// 如果other是一个集合，我们可以假设它没有重复元素，所以使用这种技术：
        /// 如果无法移除，则表示它不在此集合中，因此添加它。
        /// 
        /// 与其他方法一样，调用者负责确保other是使用相同相等比较器的哈希集。
        /// </summary>
        /// <param name="other">要进行对称差集运算的哈希集</param>
        private void SymmetricExceptWithUniqueHashSetEx(HashSetEx<T> other)
        {
            foreach (T item in other)
            {
                if (!Remove(item))
                {
                    AddIfNotPresent(item);
                }
            }
        }

        /// <summary>
        /// 实现说明：
        /// 
        /// 当other不是HashSetEx时用于对称差集运算。这更复杂，因为other可能包含重复元素。
        /// HashSetEx技术在这些情况下可能会失败：
        /// 1. Other有一个不在this中的重复元素：HashSetEx技术会先添加然后移除它。
        /// 2. Other有一个在this中的重复元素：HashSetEx技术会先移除然后重新添加它。
        /// 一般来说，每当它在other中出现时，它的存在状态就会切换一次。
        /// 
        /// 此技术使用位标记来指示是否添加/移除项目。如果已在集合中存在，
        /// 它将被标记为删除。如果从other添加，它将被标记为不应移除。
        ///
        /// </summary>
        /// <param name="other">要进行对称差集运算的可枚举集合</param>
        [SecuritySafeCritical]
        private unsafe void SymmetricExceptWithEnumerable(IEnumerable<T> other)
        {
            int originalLastIndex = m_lastIndex;
            int intArrayLength = BitHelper.ToIntArrayLength(originalLastIndex);

            BitHelper itemsToRemove;
            BitHelper itemsAddedFromOther;
            if (intArrayLength <= StackAllocThreshold / 2)
            {
                int* itemsToRemovePtr = stackalloc int[intArrayLength];
                itemsToRemove = new BitHelper(itemsToRemovePtr, intArrayLength);

                int* itemsAddedFromOtherPtr = stackalloc int[intArrayLength];
                itemsAddedFromOther = new BitHelper(itemsAddedFromOtherPtr, intArrayLength);
            }
            else
            {
                int[] itemsToRemoveArray = new int[intArrayLength];
                itemsToRemove = new BitHelper(itemsToRemoveArray, intArrayLength);

                int[] itemsAddedFromOtherArray = new int[intArrayLength];
                itemsAddedFromOther = new BitHelper(itemsAddedFromOtherArray, intArrayLength);
            }

            foreach (T item in other)
            {
                int location = 0;
                bool added = AddOrGetLocation(item, out location);
                if (added)
                {
                    // wasn't already present in collection; flag it as something not to remove
                    // *NOTE* if location is out of range, we should ignore. BitHelper will
                    // detect that it's out of bounds and not try to mark it. But it's 
                    // expected that location could be out of bounds because adding the item
                    // will increase m_lastIndex as soon as all the free spots are filled.
                    itemsAddedFromOther.MarkBit(location);
                }
                else
                {
                    // already there...if not added from other, mark for remove. 
                    // *NOTE* Even though BitHelper will check that location is in range, we want 
                    // to check here. There's no point in checking items beyond originalLastIndex
                    // because they could not have been in the original collection
                    if (location < originalLastIndex && !itemsAddedFromOther.IsMarked(location))
                    {
                        itemsToRemove.MarkBit(location);
                    }
                }
            }

            // if anything marked, remove it
            for (int i = 0; i < originalLastIndex; i++)
            {
                if (itemsToRemove.IsMarked(i))
                {
                    Remove(m_slots[i].value);
                }
            }
        }

        /// <summary>
        /// 如果尚未在哈希集中则添加。返回一个out参数，指示添加的位置索引。
        /// SymmetricExcept使用此方法，因为它需要知道以下信息：
        /// - 项目是否已存在于集合中或从other添加
        /// - 它的位置（如果已存在，它将被标记为移除，否则标记为保留）
        /// </summary>
        /// <param name="value">要添加的值</param>
        /// <param name="location">添加的位置索引</param>
        /// <returns>如果添加成功则返回true，如果已存在则返回false</returns>
        private bool AddOrGetLocation(T value, out int location)
        {
            Debug.Assert(m_buckets != null, "m_buckets is null, callers should have checked");

            int hashCode = InternalGetHashCode(value);
            int bucket = hashCode % m_buckets.Length;
            for (int i = m_buckets[hashCode % m_buckets.Length] - 1; i >= 0; i = m_slots[i].next)
            {
                if (m_slots[i].hashCode == hashCode && m_comparer.Equals(m_slots[i].value, value))
                {
                    location = i;
                    return false; //already present
                }
            }
            int index;
            if (m_freeList >= 0)
            {
                index = m_freeList;
                m_freeList = m_slots[index].next;
            }
            else
            {
                if (m_lastIndex == m_slots.Length)
                {
                    IncreaseCapacity();
                    // this will change during resize
                    bucket = hashCode % m_buckets.Length;
                }
                index = m_lastIndex;
                m_lastIndex++;
            }
            m_slots[index].hashCode = hashCode;
            m_slots[index].value = value;
            m_slots[index].next = m_buckets[bucket] - 1;
            m_buckets[bucket] = index + 1;
            m_count++;
            location = index;
            return true;
        }

        /// <summary>
        /// 确定可用于判断相等性、子集和超集的计数。这仅在other是IEnumerable而不是HashSetEx时使用。
        /// 如果other是HashSetEx，则这些属性可以更快地检查而无需使用标记，因为我们可以假设other没有重复元素。
        /// 
        /// 调用者执行以下计数检查：
        /// 1. 相等：检查unfoundCount = 0且uniqueFoundCount = m_count；即other中的所有元素都在this中，
        /// 且this中的所有元素都在other中
        /// 2. 子集：检查unfoundCount >= 0且uniqueFoundCount = m_count；即other可能有不在this中的元素，
        /// 但this中的所有元素都在other中
        /// 3. 真子集：检查unfoundCount > 0且uniqueFoundCount = m_count；即other必须至少有一个不在this中的元素，
        /// 且this中的所有元素都在other中
        /// 4. 真超集：检查unfoundCount = 0且uniqueFoundCount严格小于m_count；即other中的所有元素都在this中，
        /// 且this至少有一个不在other中的元素
        /// 
        /// 早期的实现使用委托来执行这些检查而不是返回ElementCount结构体；
        /// 但由于委托的性能开销，这一实现已被更改。
        /// </summary>
        /// <param name="other">要检查的可枚举集合</param>
        /// <param name="returnIfUnfound">允许我们在相等性和真超集检查中更快完成，
        /// 因为unfoundCount必须为0。</param>
        /// <returns>包含唯一计数和未找到计数的ElementCount结构体</returns>
        [SecuritySafeCritical]
        private unsafe ElementCount CheckUniqueAndUnfoundElements(IEnumerable<T> other, bool returnIfUnfound)
        {
            ElementCount result;

            // need special case in case this has no elements. 
            if (m_count == 0)
            {
                int numElementsInOther = 0;
                foreach (T item in other)
                {
                    numElementsInOther++;
                    // break right away, all we want to know is whether other has 0 or 1 elements
                    break;
                }
                result.uniqueCount = 0;
                result.unfoundCount = numElementsInOther;
                return result;
            }


            Debug.Assert((m_buckets != null) && (m_count > 0), "m_buckets was null but count greater than 0");

            int originalLastIndex = m_lastIndex;
            int intArrayLength = BitHelper.ToIntArrayLength(originalLastIndex);

            BitHelper bitHelper;
            if (intArrayLength <= StackAllocThreshold)
            {
                int* bitArrayPtr = stackalloc int[intArrayLength];
                bitHelper = new BitHelper(bitArrayPtr, intArrayLength);
            }
            else
            {
                int[] bitArray = new int[intArrayLength];
                bitHelper = new BitHelper(bitArray, intArrayLength);
            }

            // count of items in other not found in this
            int unfoundCount = 0;
            // count of unique items in other found in this
            int uniqueFoundCount = 0;

            foreach (T item in other)
            {
                int index = InternalIndexOf(item);
                if (index >= 0)
                {
                    if (!bitHelper.IsMarked(index))
                    {
                        // item hasn't been seen yet
                        bitHelper.MarkBit(index);
                        uniqueFoundCount++;
                    }
                }
                else
                {
                    unfoundCount++;
                    if (returnIfUnfound)
                    {
                        break;
                    }
                }
            }

            result.uniqueCount = uniqueFoundCount;
            result.unfoundCount = unfoundCount;
            return result;
        }

        /// <summary>
        /// 将此集合复制到数组中。用于调试视图
        /// </summary>
        /// <returns></returns>
        internal T[] ToArray()
        {
            T[] newArray = new T[Count];
            CopyTo(newArray);
            return newArray;
        }

        /// <summary>
        /// HashSetExEqualityComparer使用的内部方法。根据指定的比较器比较set1和set2。
        /// 
        /// 由于项目是根据特定的相等比较器进行哈希的，如果它们使用不同的相等比较器，
        /// 我们必须 resort to n^2 搜索。
        /// </summary>
        /// <param name="set1"></param>
        /// <param name="set2"></param>
        /// <param name="comparer"></param>
        /// <returns></returns>
        internal static bool HashSetExEquals(HashSetEx<T> set1, HashSetEx<T> set2, IEqualityComparer<T> comparer)
        {
            // 首先处理null情况
            if (set1 == null)
            {
                return (set2 == null);
            }
            else if (set2 == null)
            {
                // set1 != null
                return false;
            }

            // 所有比较器都相同；这样更快
            if (AreEqualityComparersEqual(set1, set2))
            {
                if (set1.Count != set2.Count)
                {
                    return false;
                }
                // 足以检查子集
                foreach (T item in set2)
                {
                    if (!set1.Contains(item))
                    {
                        return false;
                    }
                }
                return true;
            }
            else
            {  // n^2搜索，因为项目是根据各自的EC进行哈希的
                foreach (T set2Item in set2)
                {
                    bool found = false;
                    foreach (T set1Item in set1)
                    {
                        if (comparer.Equals(set2Item, set1Item))
                        {
                            found = true;
                            break;
                        }
                    }
                    if (!found)
                    {
                        return false;
                    }
                }
                return true;
            }
        }

        /// <summary>
        /// 检查相等比较器是否相等。这用于那些如果知道另一个项具有唯一元素就可以加速的算法。
        /// 即，如果它们使用不同的相等比较器，则集合之间的唯一性假设会被打破。
        /// </summary>
        /// <param name="set1"></param>
        /// <param name="set2"></param>
        /// <returns></returns>
        private static bool AreEqualityComparersEqual(HashSetEx<T> set1, HashSetEx<T> set2)
        {
            return set1.Comparer.Equals(set2.Comparer);
        }

        /// <summary>
        /// 解决对GetHashCode(null)抛出ArgumentNullException的比较器问题。
        /// </summary>
        /// <param name="item"></param>
        /// <returns>哈希码</returns>
        private int InternalGetHashCode(T item)
        {
            return m_comparer.GetHashCode(item) & Lower31BitMask;
        }

        #endregion

        // 用于依赖计数的集合检查操作（使用枚举）
        internal struct ElementCount
        {
            internal int uniqueCount;
            internal int unfoundCount;
        }

        internal struct Slot
        {
            internal int hashCode;      // 哈希码的低31位，-1表示未使用
            internal int next;          // 下一个条目的索引，-1表示最后一个
            internal T value;
        }

#if !SILVERLIGHT
        [Serializable()]
#endif
        public struct Enumerator : IEnumerator<T>, IEnumerator
        {
            private HashSetEx<T> set;
            private int index;
            private T current;

            internal Enumerator(HashSetEx<T> set)
            {
                this.set = set;
                index = 0;
                current = default(T);
            }

            public void Dispose()
            {
            }

            public bool MoveNext()
            {
                while (index < set.m_lastIndex)
                {
                    if (set.m_slots[index].hashCode >= 0)
                    {
                        current = set.m_slots[index].value;
                        index++;
                        return true;
                    }
                    index++;
                }
                index = set.m_lastIndex + 1;
                current = default(T);
                return false;
            }

            public T Current
            {
                get
                {
                    return current;
                }
            }

            Object IEnumerator.Current
            {
                get
                {
                    if (index == 0 || index == set.m_lastIndex + 1)
                    {
                        throw new InvalidOperationException();
                    }
                    return Current;
                }
            }

            void IEnumerator.Reset()
            {
                index = 0;
                current = default(T);
            }
        }
    }

}